The present invention is directed to producing document copies and in particular to verifying a copy""s provenance.
The ubiquity of photocopies and telecopiers in businesses and other environments has afforded a great deal of information-transfer convenience. Unfortunately, there are a number of situations in which this convenience is not entirely beneficial. It can make it hard to restrict copying when a confidentiality agreement, for instance, requires such a restriction. Also, photocopying can mask the fact that a document has been altered. That is, an erasure or xe2x80x9cwhite-outxe2x80x9d clearly visible in an original document may not be apparent at all in a photocopy or telecopy.
In policing photocopier or telecopier use, it would be helpful to be able to verify that a given photocopy or telecopy was actually produced by its purported source. This would help in complying with agreements not to copy and may have forensic applicability in enforcing laws against fraud.
I have developed a way of verifying document-copy provenance that is secure and easy to apply. The inventive method is a type of zero-knowledge interactive proof. Proofs of this general type are described, for instance, in Goldwasser, xe2x80x9cThe Knowledge Complexity of Interactive Proof Systems,xe2x80x9d Proc. STOC 1985.
The type of proof involved here is based on the concept of non-planar isomorphic graphs related by a secret permutation matrix. In this context, the graph can be envisioned conceptually as a set of points in space that are interconnected by xe2x80x9cedges.xe2x80x9d For the purposes of the inventive method, such a graph can be represented simply as pairs of numbers, each number being a label that uniquely identifies one of the graph""s interconnected points, or xe2x80x9cnodes.xe2x80x9d A second graph is isomorphic to the first if it would be the result of, say, simply renaming the various nodes.
Now, it is a simple matter to generate a second graph isomorphic to the first graph: one simply devices a set of unique substitutions for all of the node labels. But the reverse problem, namely, determining the xe2x80x9cpermutation matrixxe2x80x9d that specifies the replacements by which one isomorphic graph is derived from another, rapidly becomes computationally intractable with increases in the number of nodes and edges, at least if is the graphs are nonplanar, i.e., if they cannot be represented as co-planar nodes without having intersecting edges.
According to the invention, the copy machine embeds graph-defining information in the copy, preferably in a manner that is not readily detectable by human vision. Possibly together with information already existing in the document, the information specifies at least two isomorphic graphs that are related by a private permutation matrix. The permutation matrix is preferably known only to the copy-machine operator or, more typically, a xe2x80x9csmart cardxe2x80x9d that the operator owns. As another alternative, it may be stored in the copier by the copier vendor.
To verify the copy""s provenance, the verifying entity employs a publicly known technique for extracting the graphs from an image of the document copy. Then a xe2x80x9cprover,xe2x80x9d i.e., a purported source, provides a series of test graphs that should be isomorphic to the graphs extracted from the document. For each test graph, the verifier ramdomly chooses between the (typically two) extracted graphs and thereby challenges the prover to generate the permutation matrix that relates the test graph to the chosen graph. If the prover is able to produce such a permutation matrix consistently over a large number of challenges, then the verifier can have a high level of confidence that the prover is in possession of the secret permutation matrix and should therefore be the document copy""s source.
This method is highly secure, since it requires no transmission of any secret key. And, with the exception of the need for a standard method by which to extract the graphs, it requires no complicated infrastructure, such as a private-key registry.